/*  Copyright 2010 Daniel Brasil Magnani
 *  Created on: Dec 20, 2010
 *      Author: daniel
 */

#include <algorithm>
#include "exchange.h"

void Exchange::UpdateMatrices(const std::vector<Constraint> &constraint_list) {
  for (int i = 0; i < constraint_size_; i++) {
    for (int j = 0; j < solution_size_; j++) {
      M1_[i][j] = 0;
      M2_[i][j] = 0;
      M3_[i][j] = 0;
      for (int l = 0; l < constraint_list[i].p; l++) {
        if ( j+l < solution_size_ ) {
          M1_[i][j] += solution_[j+l].constraints[i];
        }
      }
      if ( M1_[i][j] > constraint_list[i].n ) {
        if ( j > 0 ) {
          M2_[i][j] = M2_[i][j-1]+1;
          M3_[i][j] = M3_[i][j-1]+1;
        } else {
          M2_[i][j] = 1;
          M3_[i][j] = 1;
        }
      } else if ( M1_[i][j] == constraint_list[i].n ) {
        if ( j > 0 ) {
          M2_[i][j] = M2_[i][j-1];
          M3_[i][j] = M3_[i][j-1]+1;
        } else {
          M2_[i][j] = 0;
          M3_[i][j] = 1;
        }
      } else {
        if ( j > 0 ) {
          M2_[i][j] = M2_[i][j-1];
          M3_[i][j] = M3_[i][j-1];
        } else {
          M2_[i][j] = 0;
          M3_[i][j] = 0;
        }
      }
    }
  }
}

int Exchange::Variation(int j, int P, int k, const std::vector<std::vector<int> > &M ) {
  int decrease = 0;
  if ( j - P >= 0 )
    decrease += M[k][j] - M[k][j-P];
  else
    decrease += M[k][j];
  return decrease;
}

Cost Exchange::ExchangeCost(int i, int j, const std::vector<Constraint> &constraint_list, int k) {
  Cost variation;
  variation.priority = 0;
  variation.nonpriority = 0;
  if ( solution_[i].constraints[k] == 0 &&
       solution_[j].constraints[k] == 1 ) {
    if ( constraint_list[k].priority == 1 ) {
      variation.priority += Variation(j, constraint_list[k].p, k, M2_);
      variation.priority -= Variation(i, constraint_list[k].p, k, M3_);
    } else {
      variation.nonpriority += Variation(j, constraint_list[k].p, k, M2_);
      variation.nonpriority -= Variation(i, constraint_list[k].p, k, M3_);
    }
  } else if ( solution_[i].constraints[k] == 1 &&
              solution_[j].constraints[k] == 0 )  {
    if ( constraint_list[k].priority == 1 ) {
      variation.priority += Variation(i, constraint_list[k].p, k, M2_);
      variation.priority -= Variation(j, constraint_list[k].p, k, M3_);
    } else {
      variation.nonpriority += Variation(i, constraint_list[k].p, k, M2_);
      variation.nonpriority -= Variation(j, constraint_list[k].p, k, M3_);
    }
  }

  return variation;
}

Exchange::Exchange(int yesterday_cars_size,
                   int constraint_list_size,
                   const std::vector<Car> &solution) {
  cost_.priority = 0;
  cost_.nonpriority = 0;
  solution_.reserve(solution.size());
  copy(solution.begin(), solution.end(), back_inserter(solution_));
  constraint_size_ = constraint_list_size;
  solution_size_ = solution_.size();
  yesterday_size_ = yesterday_cars_size;

  M1_.resize(constraint_size_);
  M2_.resize(constraint_size_);
  M3_.resize(constraint_size_);
  for (int i = 0; i < constraint_size_; i++) {
    M1_[i].resize(solution_size_);
    M2_[i].resize(solution_size_);
    M3_[i].resize(solution_size_);
  }
}

std::vector<Car> Exchange::get_solution() {
  return solution_;
}

int Exchange::ExchangeLocalSearchFirst(const std::vector<Constraint> &constraint_list) {
  int change = 1;
  Cost variation;
  Cost total_variation;

  UpdateMatrices(constraint_list);

  while ( change != 0 ) {
    change = 0;
    for ( int i = yesterday_size_; i < solution_size_; i++ ) {
      if ( change == 1 )
        break;
      for ( int j = i+1; j < solution_size_; j++ ) {
        total_variation.priority = 0;
        total_variation.nonpriority = 0;
        for ( int k = 0; k < constraint_size_; k++ ) {
          variation = ExchangeCost(i, j, constraint_list, k);
          total_variation.priority += variation.priority;
          total_variation.nonpriority += variation.nonpriority;
        }
        if ( total_variation.priority > 0 ||
            (total_variation.priority == 0 &&
             total_variation.nonpriority > 0) ) {
          std::swap(solution_[i], solution_[j]);
          change = 1;
          UpdateMatrices(constraint_list);
          break;
        }
      }
    }
  }
  return true;
}


int Exchange::ExchangeLocalSearchBest(const std::vector<Constraint> &constraint_list) {
  int change = 1;
  Cost variation;
  Cost total_variation;
  Cost variation_max;
  int u,v;

  UpdateMatrices(constraint_list);

  while ( change != 0 ) {
    change = 0;
    variation_max.priority = 0;
    variation_max.nonpriority = 0;
    for ( int i = yesterday_size_; i < solution_size_; i++ ) {
      for ( int j = i+1; j < solution_size_; j++ ) {
        total_variation.priority = 0;
        total_variation.nonpriority = 0;
        for ( int k = 0; k < constraint_size_; k++ ) {
          variation = ExchangeCost(i, j, constraint_list, k);
          total_variation.priority += variation.priority;
          total_variation.nonpriority += variation.nonpriority;
        }
        if ( total_variation.priority > variation_max.priority ||
            (total_variation.priority == variation_max.priority &&
             total_variation.nonpriority > variation_max.nonpriority) ) {
          u = i;
          v = j;
          variation_max.priority = total_variation.priority;
          variation_max.nonpriority = total_variation.nonpriority;
        }
      }
    }
    if ( variation_max.priority > 0 ||
        (variation_max.priority == 0 &&
         variation_max.nonpriority > 0) ) {
      std::swap(solution_[u], solution_[v]);
      change = 1;
      UpdateMatrices(constraint_list);
    }
  }
  return true;
}
